package leetcode_201_220;

public class rangeBitwiseAnd_201 {
    public int rangeBitwiseAnd(int left, int right) {
        //5  101
        //6  110
        //7  111
        //二进制数+1的时候，一定存在一个规律：如果末尾开始的第一个0置为1后面全部取反
        //即可以发现，连续的数字，公共前缀后边的部分极为他们的数值差异地方
        //一定不会出现某一位，所有数字都为1的情况（这种情况数字会出现重复或者不连续），最少有1个0
        //因为数字是连续的一定会出现0和1的交替变化
        //按位与只要有一个0，结果即为0，题目即等价为求left和right公共前缀的值
        int cnt=0;          //记录左移的次数
        while(left!=right){
            cnt++;
            right>>=1;
            left>>=1;
        }
        left <<= cnt;
        return left;
    }
}
